home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / objcissu.lha / krab-runopt-paper < prev    next >
Internet Message Format  |  1993-02-27  |  12KB
  1. Return-Path: <krab@iesd.auc.dk>
  2. Date: Sat, 20 Feb 1993 19:08:46 +0100
  3. From: Kresten Krab Thorup <krab@iesd.auc.dk>
  4. To: gcc2@cygnus.com
  5. Subject: Optimizing the GNU objc runtime [long]
  6.  
  7.           How to optimize the GNU objective C runtime
  8.  
  9.                         Kresten Krab Thorup
  10.                          krab@iesd.auc.dk
  11.  
  12.  
  13.     Abstract: The following is an investigation of the changes needed
  14.     to the current objc runtime, to achieve the simple but non-trivial
  15.     goal of making the messenger so short that it only does a few
  16.     fetch instructions. 
  17.  
  18.     A major problem in this is to assure the consistency when
  19.     initializing the system.  Basically--how do we catch a message
  20.     to an object which class has not yet been initialized. 
  21.  
  22.  
  23. Introduction
  24. ============
  25.  
  26. The principal goal of this investigation is to make needed changes to
  27. the current objc runtime, so that the two messengers can be written
  28. somewhat like this:
  29.  
  30.   inline IMP objc_msgSend(id receiver, SEL operation)
  31.   {
  32.     if(receiver)
  33.       return receiver->class_pointer->cache[operation];
  34.     else
  35.       <<Return IMP for sending selector `operation' to nil object>>;
  36.   }
  37.   
  38.   inline IMP objc_msgSendSuper(Super_t super, SEL operation)
  39.   {
  40.     if(super->class)
  41.       return super->class->cache[operation];
  42.     else
  43.       <<Return IMP for sending selector `operation' to nil object>>;
  44.   }  
  45.  
  46. How to handle messages to nil is not relevant for this discussion.
  47.  
  48. Most of the fetch instructions needed for these functions can possibly
  49. be eliminated if the function is used in an inline fashion.  It may
  50. for example already be known at compile time if the receiver can
  51. possibly be null.
  52.  
  53. The desire that the messenger can be coded this short was expressed
  54. clearly by Richard Stallman.  I see no need to discuss *if* it should
  55. be this simple--only *how* to do it. 
  56.  
  57.  
  58.  
  59. Initialization
  60. ==============
  61.  
  62. A major problem in achieving this goal is to keep the semantics of the
  63. user level initialization correct.  For convenience, I will summarize
  64. that in the following paragraph:
  65.  
  66.    Each class may define a factory method called "+initialize".  This
  67.    method may be used to initialize `global' data structures needed by
  68.    the class.  The method "initialize" is guaranteed to be called by
  69.    the runtime system before execution of the user level entry point
  70.    "main", and before execution of any other messages which may be
  71.    send to the class in which it resides.  "initialize" is guaranteed
  72.    to be called only once, and it may contain any kind of legal
  73.    objective C code.  Especially sending messages to other classes or
  74.    objects is also legal.   
  75.  
  76. This is quite a bit to guarantee, but it actually *is* possible to
  77. keep all those promises, still using the fast messenger.  The
  78. following sections will explain how.
  79.  
  80. Before this `user level' initialization can take place, the runtime
  81. system has initialized its internal structures.  This initialization,
  82. which I will call `runtime level initialization' include building the
  83. following data structures: 
  84.  
  85.   * Representation of classes, including the pointers to their super
  86.     classes, as well as a table for mapping class names to their
  87.     internal representation. 
  88.  
  89.   * Assign unique integers to each selector.  This is done in a
  90.     forth-running fashion, so that we will know that all selectors are
  91.     in the interval from 1 to max_selector.
  92.  
  93.   * Tables for mapping selectors to names, and for mapping names to
  94.     selectors. 
  95.  
  96.   * Tables for looking up method IMP's given a class and a selector.
  97.     This is not the dispatch table, only per-class defined methods
  98.     are present.
  99.  
  100. The `user level' initialization thus starts right after the `runtime
  101. level' initialization has been ended, by calling a function I will
  102. from now on call `__objc_initClasses'.  The job of this function is to
  103. call "initialize" for all classes, and to install the real dispatch
  104. table as used in the messenger in such a way that all the above
  105. `promises' will hold.
  106.  
  107.  
  108. The user level initialization
  109. -----------------------------
  110.  
  111. The trick of handling the `user level' initialization phase correct is
  112. to install a dummy function (which I will call __objc_initMetaClass)
  113. in the dispatch table for all factory methods before we call
  114. "initialize" for each class.  The dummy method will then initialize
  115. the receiver, install the real dispatch table, and forward the call to
  116. the method it was called for.  I will come back to how to implement
  117. this forwarding mechanism later.
  118.  
  119. To justify that it is enough to install the dummy method in entries
  120. for factory methods, observe the fact, that one cannot call a instance
  121. method in a class before some factory method has been issued for that
  122. class -- a call to `+alloc' or `+new' is needed before an instance
  123. method is relevant.
  124.  
  125. The following sections will take the form of WEB like code, in order to
  126. explain what happens step by step in a top down fashion.  
  127.  
  128. The following is the current for the `user level' initialization
  129. function.
  130.  
  131.   void __objc_initClasses()
  132.   {
  133.    <<[1] Allocate dispatch tables for all classes>>
  134.    <<[2] For each class, install __objc_initMetaClass for all factory methods>>
  135.    <<[3] For each class, install correct IMPs for all instance methods>>
  136.    <<[4] For each class, call "+initialize">>
  137.   }
  138.  
  139. We now observe, that a dispatch table for a given class is an array of
  140. pointers to functions (called IMPs) which is indexed by selector.  All
  141. dispatch tables are thus of equal size, namely the maximal number of
  142. selectors (max_selectors).  Hence the code for allocating dispatch
  143. tables is very simple:
  144.  
  145.   <<[1] Allocate dispatch tables for all classes>>=
  146.  
  147.    <<[5] For each class do>> {
  148.      /* Allocate dispatch table for instance methods */
  149.      class->cache = (IMP*)malloc((max_selector+1)*sizeof(IMP));
  150.  
  151.      /* Allocate dispatch table for factory methods */
  152.      class->class_pointer->cache = (IMP*)malloc((max_selector+1)*sizeof(IMP));
  153.    }
  154.  
  155. How to implement the iterator <<[5] For each class do>> is irrelevant.
  156. The semathics is that the variable `class' is set to point to each
  157. known class in turn, as the following body is evaluated.
  158.  
  159.  
  160.  
  161. The code for installing __objc_initMetaClass is equally simple.  How
  162. to actual implement __objc_initMetaClass will come as soon as we have
  163. finished __objc_initClasses.
  164.  
  165.   <<[2] For each class, install __objc_initMetaClass for all factory methods>>=
  166.  
  167.    <<[5] For each class do>> {
  168.      int sel;
  169.      for(sel = 0; sel <= max_selector; sel++) 
  170.        class->class_pointer->cache[sel] = __objc_initMetaClass;
  171.    }
  172.  
  173.  
  174. The code for installing real IMP's contains a bit more code.  We will
  175. here use the trick of installing a special method __objc_missingMethod
  176. at all indices for which there do not exist a corresponding message.
  177. That function handles the case where a message is not recognized, and
  178. if possible, forward the message to `doesNotRecognize:' in the
  179. receiver.  I won't discuss __objc_missingMethod further in this document.
  180.  
  181.   <<[3] For each class, install correct IMPs for all instance methods>>=
  182.  
  183.    <<[5] For each class do>> {
  184.      int sel;
  185.      for(sel = 0; sel <= max_selector; sel++) {
  186.        Method_t method = searchForMethodInHierachy(class, sel);
  187.        if(method) 
  188.      class->cache[sel] = method->method_imp;
  189.        else
  190.      class->cache[sel] = __objc_missingMethod;
  191.      }     
  192.    }
  193.      
  194. The last bit of __objc_initClasses is to call "initialize" for each class.  
  195.  
  196.   <<[4] For each class, call "+initialize">>
  197.  
  198.     SEL initialize = sel_getUID("initialize");
  199.     <<[5] For each class do>> {
  200.  
  201.       /* If this class is not yet initialized */
  202.       if((class->class_pointer->info & CLS_INITIALIZED) != CLS_INITIALIZED) {
  203.     
  204.     /* Get imp for the method */
  205.     IMP imp = objc_msgSend(class->class_pointer, initialize);
  206.  
  207.     /* Register class initialized */
  208.     class->class_pointer->info |= CLS_INITIALIZED;
  209.  
  210.     /* actually call the method */
  211.         (*imp)(class->class_pointer, initialize);
  212.       }
  213.     }
  214.  
  215.  
  216.  
  217. Managing the initialization
  218. ---------------------------
  219.  
  220. The last thing done in __objc_initClasses is to call "initialize" for
  221. each class.  When this happens, it will actually call the function
  222. __objc_initMetaClass, since we installed that function for all factory
  223. methods.  But! If an "initialize" method calls a factory method in a
  224. yet uninitialized class, this function will also catch the
  225. invocation.  In the latter case, it is the job of this function to
  226. perform an "initialize" on the class.  Remember, that this function
  227. will only be invoked with a class as its first element since it's only
  228. installed in the table of factory methods.
  229.  
  230.    id __objc_initMetaClass(Class_t class, SEL operation, ...)
  231.    {
  232.      SEL initialize = sel_getUID("initialize");
  233.    
  234.      <<[6] For `class', install correct IMPs for all factory methods>>;
  235.    
  236.      if(operation != initialize) {
  237.        /* Get imp for the method */
  238.        IMP imp = objc_msgSend(class->class_pointer, initialize);
  239.    
  240.        /* Register class initialized */
  241.        class->class_pointer->info |= CLS_INITIALIZED;
  242.    
  243.        /* actually call the method */
  244.        (*imp)(class->class_pointer, initialize);
  245.      }
  246.    
  247.      __builtin_forward(objc_msgSend(class, operation));
  248.    }  
  249.  
  250. Installing the correct factory methods is close to what we've seen
  251. before:
  252.  
  253.  
  254.   <<[6] For `class', install correct IMPs for all factory methods>>=
  255.  
  256.    {
  257.      int sel;
  258.      for(sel = 0; sel <= max_selector; sel++) {
  259.        Method_t method = searchForMethodInHierachy(class->class_pointer, sel);
  260.        if(method) 
  261.      class->class_pointer->cache[sel] = method->method_imp;
  262.        else
  263.      class->class_pointer->cache[sel] = __objc_missingMethod;
  264.      }     
  265.    }
  266.      
  267. This completes my discussion on initialization.  It should be clear to
  268. the reader, that the present code will actually do the initialization 
  269. according to the specification.  The only missing link is how to
  270. implement the __builtin_forward, which is covered in the following section.
  271.  
  272.  
  273.  
  274. Forwarding messages
  275. ===================
  276.  
  277. For the purpose of implementing the fast messenger as described above,
  278. we will need the ability to do a simple kind of forwarding.  The need
  279. is to have a special builtin function, which can `call' another
  280. function with the frame of the enclosing function.  This `call' should
  281. really be a `goto' or `jump' instruction, which is done in the context
  282. present right after the prologue of the enclosing function.
  283.  
  284. In order to describe what this really means, I will assume, that we
  285. have another builtin function, which will take a block of C code, and
  286. place it right after the prologue of the enclosing function.  This is
  287. somewhat like what __builtin_saveregs does.  This builtin will have
  288. the following form:
  289.  
  290.   __builtin_addprologue <Statement>;
  291.  
  292. Where <Statement> may be any statement including compound statements,
  293. and control structures like `if' and `while'.  To make myself clear,
  294. the semantics of __builtin_saveregs can be expressed like:
  295.  
  296.   #define __builtin_saveregs() \
  297.     __builtin_addprologue __builtin_saveregs(); /* don't expand */
  298.  
  299. Now for the meaning of __builtin_forward.  The following is to be
  300. regarded as pseudo code, since I'm not sure if this is really the
  301. exact way to do it.  We will assume that the following two global
  302. variables are present in the runtime.
  303.  
  304.   jmp_buf  __objc_forward_env; 
  305.   void    *__objc_forward_imp;
  306.  
  307. The actual code could be done as the following macro.  For clarity, I
  308. did not add \<nl> to the definition.
  309.  
  310.   #define __builtin_forward(imp)           /* argument is an IMP */
  311.     __builtin_addprologue {
  312.       if(setjmp(__objc_forward_env) == 1)
  313.         goto *__objc_forward_imp;          /* non-local goto */
  314.     }
  315.     __objc_forward_imp = (void*)imp;
  316.     longjmp(__objc_forward_env, 1);
  317.  
  318. It must be implemented as a macro, since otherwise the
  319. __builtin_addprologue would cause the code to be added inside the
  320. __builtin_forward function.  I hope this code makes it clear what I
  321. mean. 
  322.  
  323.  
  324.